package com.tlvip.leetcode;

/**
 * <p>description：</p>
 * <p>copyright： copyright(C)2016-2099</p>
 * <p>Life is short,we need passion</p>
 * <p>Summary：
 * 在不实用sqrt(x)函数的情况下，得到x的平方根正数部分
 * 二分法、牛顿迭代</p>
 * <p>instructions： </p>
 * Date 2022/5/9</p>
 * Author mac
 *
 * @version 1.0
 */
public class GetSqrt {
    public static void main(String[] args) {
//        System.out.println(getSqrt(9));
        System.out.println(sqrtByND(6));
        System.out.println(sqrtByND(8));
        System.out.println(sqrtByND(9));
        System.out.println(sqrtByND(10));
    }

    /**
     * 牛顿迭代解决问题
     * <p>
     * 如果 x^2 = n 则 x = n/x
     * 不断迭代求解最优解
     *
     * @param x 给定的数字
     * @return 返回平方根
     */
    public static int sqrtByND(int x) {
        if (x <= 0) {
            return x;
        }
        return (int) sqrt(x, x);
    }

    public static double sqrt(double i, int x) {
        double res = (i + x / i) / 2;
        if (res == i) {
            return i;
        } else {
            return sqrt(res, x);
        }
    }

    /**
     * 使用二分查找法解决问题
     *
     * @param num 给定的数字
     * @return 返回平方根正数部分
     */
    public static int getSqrt(int num) {
        if (num < 0) {
            return -1;
        }
        if (num == 0 || num == 1) {
            return num;
        }
        int index = -1, l = 0, r = num;
        while (l <= r) {
            // 取中间数 = l + (r-l)/2
            int mid = l + (r - l) / 2;
            if (mid * mid <= num) {
                index = mid;
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }
        return index;
    }
}
